// 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
// 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

// 输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
// 输出：13



// 类似合并K个有序链表；
// 模拟小顶堆，不断将根节点的元素弹出，同时更新堆
typedef struct {
    int idx;    //数组中的下标
    //矩阵中长度统一，可以不用记录每个数组的长度
    int *map;   //数组映射
} list_t;

list_t **heap_create(int** matrix, int matrixSize)
{  
    list_t **heap = malloc(sizeof(list_t *)*matrixSize);
    for (int i = 0; i < matrixSize; i++) {
        heap[i] = malloc(sizeof(list_t));
        heap[i]->idx = 0;
        heap[i]->map = &matrix[i][0];
    }
    return heap;
}

int min_idx(list_t **heap, int i, int len)
{
    int lchild = (i*2)+1, rchild = (2*i)+2; //堆中的下标
    int min = i;
    if (lchild < len && heap[lchild]->map[heap[lchild]->idx] < heap[min]->map[heap[min]->idx]) min = lchild;
    if (rchild < len && heap[rchild]->map[heap[rchild]->idx] < heap[min]->map[heap[min]->idx]) min = rchild;
    return min;
}
void swap(list_t **a, list_t **b) {
    list_t *t = *a; *a = *b; *b = t;
}
void heapify_sink(list_t **heap, int i, int len) 
{
    int min = min_idx(heap, i, len);
    if (min != i) { // 调整heap
        swap(&heap[min], &heap[i]);
        heapify_sink(heap, min, len);
    }
}

int kthSmallest(int** matrix, int matrixSize, int* matrixColSize, int k){
    // 构造小顶堆
    list_t **heap = heap_create(matrix, matrixSize);
    int heap_len = matrixSize;
    for (int i = heap_len/2; i >= 0; i--)
        heapify_sink(heap, i, heap_len);

    int tmp, len = matrixColSize[0]; 
    for (int i = 0; i < k; i++) {//将前k-1个值丢弃
        if (heap[0]->idx < len) {
            tmp = heap[0]->map[heap[0]->idx];
            heap[0]->idx++;  // 根节点弹出一个元素

            if (heap[0]->idx == len) {   // 已经全部弹出, 调整节点
                //heap[0] = heap[heap_len-1];   //直接调整heap[0]指针，会使原来的内容丢失，无法free
                swap(&heap[0], &heap[heap_len-1]);  
                heap_len--;
            }
        }
        heapify_sink(heap, 0, heap_len);
    }
    // heap_destroy(heap, matrixSize);
    for (int i = 0; i < matrixSize; i++) 
        free(heap[i]);
    free(heap);

    return tmp;
}